//设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。 
//
// 实现 Twitter 类： 
//
// 
// Twitter() 初始化简易版推特对象 
// void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函
//数都会使用一个不同的 tweetId 。 
// List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是
//由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。 
// void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 
//followeeId 的用户。 
// void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 
//followeeId 的用户。 
// 
//
// 
//
// 示例： 
//
// 
//输入
//["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", 
//"unfollow", "getNewsFeed"]
//[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
//输出
//[null, null, [5], null, null, [6, 5], null, [5]]
//
//解释
//Twitter twitter = new Twitter();
//twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5)
//twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
//twitter.follow(1, 2);    // 用户 1 关注了用户 2
//twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
//twitter.getNewsFeed(1);  // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 
//id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的
//twitter.unfollow(1, 2);  // 用户 1 取消关注了用户 2
//twitter.getNewsFeed(1);  // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用
//户 2 
//
// 
//
// 提示： 
//
// 
// 1 <= userId, followerId, followeeId <= 500 
// 0 <= tweetId <= 10⁴ 
// 所有推特的 ID 都互不相同 
// postTweet、getNewsFeed、follow 和 unfollow 方法最多调用 3 * 10⁴ 次 
// 
// Related Topics设计 | 哈希表 | 链表 | 堆（优先队列） 
//
// 👍 303, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.*;

class DesignTwitter {
    public static void main(String[] args) {
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Twitter {
        // 参照labuladong：https://labuladong.github.io/algo/2/22/66/

        public int timestamp = 0; // 时间戳

        // 推文信息类
        class Tweet {
            private int id;     // 推文id
            private int time;   // 发送推文的时间
            private Tweet next; // 指向下一条推文

            public Tweet(int id, int time) {
                this.id = id;
                this.time = time;
                this.next = null;
            }
        }

        // 用户类
        class User {
            private int id;                 // 用户id
            private Set<Integer> followed;  // 关注的用户，使用set（用户不能重复关注）
            private Tweet head;             // 该用户发送的推文头节点

            public User(int userId) {
                this.id = userId;
                this.followed = new HashSet<>();
                this.head = null;
                // 关注自己
                follow(id);
            }

            // 关注一个用户
            public void follow(int userId) {
                followed.add(userId);
            }

            // 取关（自己不能取关自己）
            public void unFollow(int userId) {
                if (userId != this.id) {
                    followed.remove(userId);
                }
            }

            // 发送一条推文
            public void post(int tweetId) {
                Tweet tweet = new Tweet(tweetId, timestamp);
                // 时间戳加一
                timestamp++;
                // 将新建的推文插入链表头
                // 越靠前的推文 time 值越大
                tweet.next = head;
                head = tweet;
            }

        }

        // 使用map将用户id和用户信息关联起来
        Map<Integer, User> map;

        public Twitter() {
            map = new HashMap<>();
        }

        // 发送一条推文
        public void postTweet(int userId, int tweetId) {
            // 没有该用户，新建该用户
            if (!map.containsKey(userId)) {
                User user = new User(userId);
                map.put(userId, user);
            }

            // 发送推文
            map.get(userId).post(tweetId);
        }

        // 获取该用户关注人的前十条推文（按照时间排序）
        public List<Integer> getNewsFeed(int userId) {
            // 保存结果
            LinkedList<Integer> res = new LinkedList<>();
            if (!map.containsKey(userId)) return res;
            Set<Integer> followed = map.get(userId).followed;
            // 按照时间从大到小进行排序
            PriorityQueue<Tweet> queue = new PriorityQueue<>((a, b) -> b.time - a.time);
            // 找到关注链表的所有用户的推文头指针
            for (Integer followId : followed) {
                Tweet head = map.get(followId).head;
                if (head == null) continue;
                queue.add(head);
            }

            while (!queue.isEmpty()) {
                // 达到10条停止
                if (res.size() == 10) {
                    break;
                }

                Tweet tweet = queue.poll();
                res.add(tweet.id);
                // 将下一条推文入队，进行排序，相当于合并多个升序链表
                Tweet nextTweet = tweet.next;
                if (nextTweet != null) {
                    queue.offer(nextTweet);
                }
            }

            return res;
        }

        // 关注他人
        public void follow(int followerId, int followeeId) {
            // 没有用户都新建
            if (!map.containsKey(followerId)) {
                User follower = new User(followerId);
                map.put(followerId, follower);
            }

            if (!map.containsKey(followeeId)) {
                User followee = new User(followeeId);
                map.put(followeeId, followee);
            }

            map.get(followerId).follow(followeeId);
        }

        // 取关他人
        public void unfollow(int followerId, int followeeId) {
            // 该用户存在才能进行取关他人
            if (map.containsKey(followerId)) {
                map.get(followerId).unFollow(followeeId);
            }
        }
    }

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
